package com.zjsru.plan2023.oneday.oneDay202301;

/**
 * @Author: CookLee
 * @Date: 2023/1/15
 * 给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。
 *
 * 对 nums 执行下述算法：
 *
 * 设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
 * 对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
 * 对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
 * 用 newNums 替换 nums 。
 * 从步骤 1 开始 重复 整个过程。
 * 执行算法后，返回 nums 中剩下的那个数字。
 *
 * 输入：nums = [1,3,5,2,4,8,2,2]
 * 输出：1
 * 解释：重复执行算法会得到下述数组。
 * 第一轮：nums = [1,5,4,2]
 * 第二轮：nums = [1,4]
 * 第三轮：nums = [1]
 * 1 是最后剩下的那个数字，返回 1 。
 *
 * 输入：nums = [3]
 * 输出：3
 * 解释：3 就是最后剩下的数字，返回 3 。
 *
 */
public class MinMaxGame {
    
    /**
     * 递归
     *
     * @param nums 数组
     * @return int
     */
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] newNums = new int[n / 2];
        for (int i = 0; i < newNums.length; i++) {
            if (this.helper(i)) {
                newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        //递归调用
        return this.minMaxGame(newNums);
    }
    
    /**
     * 判断奇偶数助手
     *
     * @param n n
     * @return boolean
     */
    private boolean helper(int n) {
        if (n % 2 == 0) {
            return true;
        }
        return false;
    }
    
    /**
     * 模拟，不采用递归调用，用循环判断直到数组的长度为1
     *
     * @param nums 全国矿工工会
     * @return int
     */
    public int minMaxGame2(int[] nums) {
        int n = nums.length;
        while (n != 1) {
            int[] newNums = new int[n / 2];
            for (int i = 0; i < newNums.length; i++) {
                if (i % 2 == 0) {
                    newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            nums = newNums;
            n /= 2;
        }
        return nums[0];
    }
    
    public static void main(String[] args) {
        MinMaxGame minMaxGame = new MinMaxGame();
        int[] nums = new int[] {1, 3, 5, 2, 4, 8, 2, 2};
        System.out.println(minMaxGame.minMaxGame(nums));
    }
}
